
#ifndef HASH_MAP_H_
#define HASH_MAP_H_

#include "arraylist.h"

namespace core
{

template <typename HashKey, typename ValueType>

class hashmap
{
public:
	template <typename HashKey, typename ValueType>
	class HashData
	{
	public:
		HashData() : value_(NULL){}
		HashKey key_;
		ValueType value_;
	};

	explicit hashmap(int capacity = 16, float loadFactor = 0.75f) : capacity_(capacity), loadFactor_(loadFactor), count_(0)
	{
		Assert(capacity_ > 0);
		maxSize_ = (int)(capacity_ * loadFactor_);
		array_ = new HashItem<HashKey, ValueType>[capacity_];
	}

	~hashmap()
	{
		Assert(count_ == 0);
		delete[] array_;
	}

	void cloneTo(hashmap* destination) const
	{
		Assert(destination->getCount() == 0);
		destination->loadFactor_ = loadFactor_;
		destination->setCapacity(capacity_);
		for(int i = 0; i < capacity_; i++)
		{
			HashItem<HashKey, ValueType>* item = &array_[i];
			if(item->value_ == NULL){ continue; }
			while(true)
			{
				destination->put(item->key_, item->value_);
				item = item->next_;
				if(item == NULL){ break; }
			}
		}
	}

	int size() const{ return count_; }
	bool empty() const{ return (count_ == 0); }

	ValueType get(const HashKey& key) const
	{
		unsigned int hashCode = key.getHashCode();
		HashItem<HashKey, ValueType>* item;
		item = &array_[hashCode % capacity_];
		if(item->value_ == NULL){ return NULL; }
		while(true)
		{
			if(item->key_.equals(key)){ return item->value_; }
			item = item->next_;
			if(item == NULL){ return NULL; }
		}
	}

	int getCapacity() const{ return capacity_; }
	float getLoadFactor() const{ return loadFactor_; }

	void toArray(array< HashData<HashKey, ValueType> >* arrayList) const
	{
		if(count_ == 0){ return; }
		arrayList->clear(count_);
		for(int i = 0; i < capacity_; i++)
		{
			HashItem<HashKey, ValueType>* item = &array_[i];
			if(item->value_ == NULL){ continue; }
			while(true)
			{
				HashData<HashKey, ValueType> data;
				data.key_ = item->key_;
				data.value_ = item->value_;
				arrayList->add(data);
				item = item->next_;
				if(item == NULL){ break; }
			}
		}
	}

	bool put(HashKey key, ValueType value)
	{
		Assert(value != NULL);
		if(value == NULL){ return false; }

		if(count_ + 1 > maxSize_)
		{
			int newCapacity = capacity_ * 2;
			while(true)
			{
				maxSize_ = (int)(newCapacity * loadFactor_);
				if(count_ + 1 <= maxSize_){ break; }
				newCapacity *= 2;
			}
			setCapacity(newCapacity);
		}

		unsigned int hashCode = key.getHashCode();

		HashItem<HashKey, ValueType>* item;
		item = &array_[hashCode % capacity_];
		if(item->value_ == NULL)
		{
			item->key_ = key;
			item->value_ = value;
			count_++;
			return true;
		}
		while(true)
		{
			if(item->key_.equals(key)){ return false; }

			if(item->next_ == NULL)
			{
				HashItem<HashKey, ValueType>* newItem;
				newItem = new HashItem<HashKey, ValueType>(key, value);
				item->next_ = newItem;
				count_++;
				return true;
			}
			item = item->next_;
		}
	}

	ValueType remove(HashKey key)
	{
		unsigned int hashCode = key.getHashCode();
		HashItem<HashKey, ValueType>* item = &array_[hashCode % capacity_];
		if(item->value_ == NULL){ return NULL; }
		ValueType returnValue = NULL;
		if(item->key_.equals(key))
		{
			returnValue = item->value_;
			if(item->next_ == NULL)
			{
				item->value_ = NULL;
				item->key_ = HashKey();
			}
			else
			{
				HashItem<HashKey, ValueType>* nextItem = item->next_;
				*item = *nextItem;
				delete nextItem;
			}
			count_--;
			return returnValue;
		}

		HashItem<HashKey, ValueType>* nextItem;
		while(true)
		{
			nextItem = item->next_;
			if(nextItem == NULL){ return NULL; }
			if(nextItem->key_.equals(key))
			{
				returnValue = nextItem->value_;
				item->next_ = nextItem->next_;
				delete nextItem;
				count_--;
				return returnValue;
			}
			item = nextItem;
		}
	}

	void clear()
	{
		for(int i = 0; i < capacity_; i++)
		{
			HashItem<HashKey, ValueType>* item = &array_[i];
			HashItem<HashKey, ValueType>* nextItem = item->next_;
			if(item->value_ == NULL){ continue; }
			item->key_ = HashKey();
			item->value_ = NULL;
			item->next_ = NULL;
			count_--;
			while(true)
			{
				item = nextItem;
				if(item == NULL){ break; }
				nextItem = item->next_;
				item->key_ = HashKey();
				item->value_ = NULL;
				item->next_ = NULL;
				count_--;
				delete item;
			}
		}
	}

	void setCapacity(int capacity)
	{
		hashmap<HashKey, ValueType*> hashMap(capacity, loadFactor_);
		int listSize = count_, listCounter = 0;
		HashKey* keyList = new HashKey[listSize];
		ValueType* valueList = new ValueType[listSize];
		for(int i = 0; i < capacity_; i++)
		{
			HashItem<HashKey, ValueType>* item = &array_[i];
			if(item->value_ == NULL){ continue; }
			while(true)
			{
				keyList[listCounter] = item->key_;
				valueList[listCounter] = item->value_;
				listCounter++;
				item = item->next_;
				if(item == NULL){ break; }
			}
		}
		clear();
		delete[] array_;
		capacity_ = capacity;
		maxSize_ = (int)(capacity_ * loadFactor_);
		array_ = new HashItem<HashKey, ValueType>[capacity_];

		for(int i = 0;i < listSize;i++){ put(keyList[i], valueList[i]); }
		delete[] keyList;
		delete[] valueList;
	}

	void trim()
	{
		int newCapacity = 1, maxSize;
		while(true)
		{
			maxSize = (int)(newCapacity * loadFactor_);
			if(count_ <= maxSize){ break; }
			newCapacity *= 2;
		}
		setCapacity(newCapacity);
	}

#ifdef _DEBUG

	void debugPrint(bool detail)
	{
		DebugOut("\nCapacity %d, LoadFactor %.2f MaxSize %d Size %d ", capacity_, loadFactor_, maxSize_, count_);
		if(detail){ DebugOut("\n"); }
		int allocCount = 0;
		for(int i = 0;i < capacity_;i++)
		{
			HashItem<HashKey, ValueType>* item = &array_[i];
			int count = 0;

			while(true)
			{
				count++;
				if(count >= 2){ allocCount++; }
				if(detail)
				{
					if(item->value_ != NULL){ DebugOut("*"); }
				}	
				if(item->next_ == NULL){ break; }
				item = item->next_;
			}
			if(detail){ DebugOut("\n"); }
		}
		DebugOut("allocCount %d allocRate %.1f%%\n", allocCount, (float)allocCount / count_ * 100.f);
	}
#endif

private:
	template <typename HashKey, typename ValueType>
	class HashItem
	{
	friend class hashmap;
	public:
		HashItem() : key_(), value_(NULL), next_(NULL){}

		HashItem(HashKey key, ValueType value) : key_(), value_(value), next_(NULL)
		{
			key_ = key;
		}

		HashItem& operator =(const HashItem& copy)
		{
			key_ = copy.key_;
			value_ = copy.value_;
			next_ = copy.next_;
			return *this;
		}

		HashKey key_;
		ValueType value_;
		HashItem* next_;
	};

	hashmap(const hashmap& copy);
	void operator =(const hashmap& copy);

	int capacity_;
	float loadFactor_;
	int maxSize_;
	int count_;
	HashItem<HashKey, ValueType>* array_;
};

}
#endif
